perm filename PLNR.RPO[UP,DOC] blob
sn#360851 filedate 1978-06-10 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00002 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 Micro-Planner Reference Manual
C00107 ENDMK
C⊗;
Micro-Planner Reference Manual
by
Gerald Jay Sussman and Terry Winograd
(edited for Stanford AI Project)
I. Introduction
1) Micro-Planner is an implementation of a subset of Carl Hewitt's
language, PLANNER, by Gerald Jay Sussman, Terry Winograd, and Eugene
Charniak in LISP. Micro-Planner is now a publically accessible
systems program of the Stanford AI project time share system. The
current version of Micro-Planner, embedded in an allocated LISP, may
be obtained by incanting "R PLNR <carriage return>" at monitor level.
Micro-Planner is also available as EXPR code or LAP code. All
questions, suggestions, or comments about Micro-Planner should be
directed to Richard Orban (login name RPO) who will maintain the
current version of the program from MIT's AI group.
2) Philosophical Overview
The "level" of a programming language is a term which is in
fairly common usage in the computer culture. We all agree, for
example, that FORTRAN, LISP, and PL/1 are higher level languages than,
say assembly language, regardless of our opinions of their relative
merits for expressing our individual styles of programming. After
some introspection, I decided that what is meant by the level of a
language is the amount of knowledge of programming style implicit in
the language processor and thus the quantity of detail which the user
does not explicitly have to specify because he may assume that the
processor will fill in for him. When we express the value judgement
that LISP or PL1, for example, is a lousy language, what we mean is
that the stylistic assumptions made by the designers of the language
are incompatible with our own styles and thus overly restrict us.
There are some of us (may PURGER preserve their file directories!)
with whom any restrictions are incompatible and who thus always write
in assembly language. There are others, such as I, who find such
restrictions an aid in the organization of large programs. Thus, to
me, LISP is useful in that it provides a large library of subroutines
with uniform calling sequences, a convenient evaluator for defining
recursively reentrant procedures from those primitives and a
bookkeeper for the maintenance of a list structured data base. Indeed
for these conveniences I pay heavily in space and time efficiency, as
well as in some feeling of constrained style.
PLANNER is the first of perhaps a whole new level of
languages which will basically be oriented toward the accomplishment
of tasks (or goals) which may in fact be broken down into subtasks
(subgoals). By contrast, in previous languages (as LISP) problem
solutions are expressed in terms of procedures (functions). The
micro-PLANNER MANUAL 1
distinction is not immediately apparent but should become more clear
if we note that in a PLANNER program, if a goal is activated then it
may be satisfied by any number of objects in the data base or by any
number of theorems (the analogue of procedure). A backup mechanism is
provided so that one of the possibilities is tried, and then if, as a
consequence a failure occurs, then another is tried, etc.
Furthermore, the data and theorems need not be referenced explicitly,
but rather by saying, in essence, "the datum (or procedure)" which
fits the following pattern (or accomplishes the desired result). In
order for such data and theorems to be implicitly referenced
efficiently the system has the responsibility of constructing and
accessing a cross-referenced data base of data and theorems.
micro-PLANNER MANUAL 2
II. Programming in Micro-Planner
The easiest way to understand Micro-Planner is to watch how
it works, so in this section we will present a few simple examples
and explain the use of some of its most elementary features.
First we will take the most venerable of traditional deductions:
Turing is a human
All humans are fallible
so
Turing is fallible.
It is easy enough to see how this could be expressed in the
usual logical notation and handled by a uniform proof procedure.
Instead, let us express it in one possible way to Micro-Planner by
saying:
(THASSERT (HUMAN TURING))
(DEFPROP THEOREM1
(THCONSE (X) (FALLIBLE (THV X))
(THGOAL (HUMAN (THV X))))
THEOREM)
(THASSERT THEOREM1)
The proof would be generated by asking Micro-Planner to
evaluate the expression:
(THGOAL (FALLIBLE TURING) (THTBF THTRUE))
We immediately see several points. First, there are two
different ways of storing information. Simple assertions are stored
in a data base of assertions, while more complex sentences containing
quantifiers or logical connectives are expressed in the form of
theorems.
Second, one of the most important points about Micro-Planner
is that it is an evaluator for statements written in a programming
language. It accepts input in the form of expressions written in the
Micro-Planner language, and evaluates them, producing a value and
side effects. THASSERT is a function which, when evaluated, stores
its argument in the data base of assertions or the data base of
theorems (which are cross-referenced in various ways to give the
system efficient look-up capabilities). A theorem is defined with
DEFPROP as are functions in LISP. In this example we have defined a
theorem of the THCONSE type (THCONSE means consequent; we will see
other types later). This states that if we ever want to establish a
goal of the form (FALLIBLE (THV X)), we can do this by accomplishing
the goal (HUMAN (THV X)), where X is a variable. The strange
function, THV, is the way of specifying that X is a variable and not
a constant as HUMAN is, and is part of Micro-Planner's pattern
matching capabilities. If we ask Micro-Planner to prove a goal of the
micro-PLANNER MANUAL 3
form (A X), there is no obvious way of knowing whether A and X are
constants (like TURING and HUMAN in the example) or variables. LISP
solves this problem by using the function QUOTE to indicate
constants. In pattern matching this is inconvenient and makes most
patterns much bulkier and more difficult to read. Instead,
Micro-Planner uses the opposite convention -- a constant is
represented by the atom itself, while a variable must be indicated by
adding an appropriate function. This function differs according to
the exact use of the variable in the pattern, but for the time being
let us just accept THV as a function indicating a variable. The
definition of the theorem indicates that it has one variable, X by
the (X) following THCONSE.
The fourth statement illustrates the function THGOAL, which
calls the Micro-Planner interpreter to try to prove an assertion.
This can function in several ways. If we had asked Micro-Planner to
evaluate (THGOAL (HUMAN TURING)) it would have found the requested
assertion immediately in the data base and succeeded (returning as
its value some indicator that it had succeeded). However, (FALLIBLE
TURING) has not been asserted, so we must resort to theorems to prove
it. Later we will see that a THGOAL statement can give Micro-Planner
various kinds of advice on which theorems are applicable to the goal
and should be tried. For the moment, (THTBF THTRUE) is advice that
causes the evaluator to try all theorems whose consequent is of a
form which matches the goal. (i.e. a theorem with a consequent ((THV
Z) TURING) would be tried, but one of the form (HAPPY (THV Z)) or
(FALLIBLE (THV Y) (THV Z)) would not. Assertions can not have an
arbitrary list structure for their format but they are not limited to
two-member lists or three-member lists as in these examples.) The
theorem we have just defined would be found, and in trying it, the
match of the consequence to the goal would cause the variable (THV X)
to be assigned to the constant TURING. Therefore, the theorem sets
up a new goal (HUMAN TURING) and this succeeds immediately since it
is in the data base. In general, the success of a theorem will
depend on evaluating a Micro-Planner program of arbitrary complexity.
In this case it contains only a single THGOAL statement, so its
succeess causes the entire theorem to succeed, and the goal (FALLIBLE
TURING) is proved.
Consider the question "Is anything fallible?", or in logic
(EXISTS (Y)(FALLIBLE Y)). This requires a variable and it could be
expressed in Micro-Planner as:
(THPROG (Y) (THGOAL (FALLIBLE (THV Y))))
Notice that THPROG (Micro-Planner's equivalent of a LISP
PROG, complete with GO statements, tags, RETURN, etc.) acts as an
existential quantifier. It provides a binding-place for the variable
Y, but does not initialize it -- it leaves it in a state particularly
marked as unassigned. To answer the question, we ask Micro-Planner to
evaluate the entire THPROG expression above. To do this it starts by
evaluating the THGOAL expression. This searches the data base for an
assertion of the form (FALLIBLE (THV Y)) and fails. It then looks
for a theorem with a consequent of that form, and finds the theorem
micro-PLANNER MANUAL 4
we defined above. Now when the theorem is called, the variable X in
the theorem is identified with the variable Y in the goal, but since
Y has no value yet, X does not receive a value. The theorem then
sets up the goal (HUMAN (THV X)) with X as a variable. The data-base
searching mechanism takes this as a command to look for any assertion
which matches that pattern (i.e. an instantiation), and finds the
assertion (HUMAN TURING). This causes X (and therefore Y) to be
assigned to the constant TURING, and the theorem succeeds, completing
the proof and returning the value (FALLIBLE TURING).
There seems to be something missing. So far,the data base
has contained only the relevant objects, and therefore Micro-Planner
has found the right assertions immediately. Consider the problem we
would get if we added new information by evaluating the statements:
(THASSERT (HUMAN SOCRATES))
(THASSERT (GREEK SOCRATES))
Our data base now contains the assertions:
(HUMAN TURING)
(HUMAN SOCRATES)
(GREEK SOCRATES)
and the theorem:
(THCONSE (X) (FALLIBLE (THV X))
(THGOAL (HUMAN (THV X))))
What if we now ask, "Is there a fallible Greek?" In
Micro-Planner we would do this by evaluating the expression:
(THPROG (X) (THGOAL (FALLIBLE (THV X))) (THGOAL (GREEK (THV X))))
THPROG acts like an AND, insisting that all of its terms are
satisfied before the THPROG is happy. Notice what might happen. The
first THGOAL may be satisfied by the exact same deduction as before,
since we have not removed information. If the data-base searcher
happens to run into TURING before it finds SOCRATES, the goal (HUMAN
(THV X)) will succeed, assigning (THV X) to TURING. After (FALLIBLE
(THV X)) succeds, the THPROG will then establish the new goal (GREEK
TURING), which is doomed to fail since it has not been asserted, and
there are no applicable theorems. If we think in LISP terms, this is
a serious problem, since the evaluation of the first THGOAL has been
completed before the second one is called, and the "push-down list"
now contains only the THPROG. If we try to go back to the beginning
and start over, it will again find TURING and so on, ad infinitum.
One of the most important features of the Micro-Planner language is
that backup in case of failure is always possible, and moreover this
backup can go to the last place where a decision of any sort was
made. Here, the decision was to pick a particular assertion from the
data base to match a goal. Other decisions might be the choice of a
theorem to satisfy a goal, or a decision of other types found in more
micro-PLANNER MANUAL 5
complex Micro-Planner functions. Micro-Planner keeps enough
information to change any decision and send evaluation back down a
new path. In our example the decision was made inside the
theorem for FALLIBLE, when the goal (HUMAN (THV X)) was matched to
the assertion (HUMAN TURING). Micro-Planner will retrace its steps,
try to find a different assertion which matches the goal, find (HUMAN
SOCRATES), and continue with the proof. The theorem will succeed
with the value (FALLIBLE SOCRATES), and the THPROG will proceed to
the next expression, (THGOAL (GREEK (THV X))). Since X has been
assigned to SOCRATES, this will set up the goal (GREEK SOCRATES)
which will succeed immediately by finding the corresponding assertion
in the data base. Since there are no more expressions in the THPROG,
it will succeed, returning as its value the value of the last
expression, (GREEK SOCRATES). The whole course of the deduction
process depends on the failure mechanism for backing up and trying
things over (this is actually the process of trying different
branches down the subgoal tree.) All of the functions like THCOND,
THAND, THOR, etc. are controlled by success vs. failure. Thus it is
the Micro-Planner executive which establishes and manipulates
subgoals in looking for a proof.
Although Micro-Planner is written as a programming language,
it differs in several critical ways from anything which is normally
considered a programming language. First, it is goal-directed.
Theorems can be thought of as subroutines, but they can be called by
specifying the goal which is to be satisfied. This is like having
the abilitiy to say "Call a subroutine which will achieve the desired
result at this point." Second, the evaluator has the mechanism of
success and failure to handle the exploration of the subgoal tree.
Other evaluators, such as LISP, with a basic recursive evaluator have
no way to do this. Third, Micro-Planner contains a bookkeeping
system for matching patterns and manipulating a data base, and for
handling that data base efficiently.
How is Micro-Planner different from a theorem prover? What is
gained by writing theorems in the form of programs, and giving them
power to call other programs which manipulate data? The key is in
the form of the data the theorem-prover can accept. Most systems
take declarative information, as in predicate calculus. This is in
the form of expressions which represent "facts" about the world.
These are manipulated by the theorem-prover according to some fixed
uniform process set by the system. Micro-Planner can make use of
imperative information, telling it how to go about proving a subgoal,
or to make use of an assertion. This produces what is called
hierarchical control structure. That is, any theorem can indicate
what the theorem prover is supposed to do as it continues the proof.
It has the full power of a general programming language to evaluate
functions which can depend on both the data base and the subgoal
tree, and to use its results to control the further proof by making
assertions, deciding what theorems are to be used, and specifying a
sequence of steps to be followed. What does this mean in practical
terms? In what way does it make a "better" theorem prover? We will
micro-PLANNER MANUAL 6
give several examples of areas where the approach is important.
First, consider the basic problem of deciding what subgoals
to try in attempting to satisfy a goal. Very often, knowledge of the
subject matter will tell us that certain methods are very likely to
succeed, others may be useful if certain other conditions are
present, while others may be possibly valuable, but not likely. We
would like to have the ability to use heuristic programs to determine
these facts and direct the theorem prover accordingly. It should be
able to direct the search for goals and solutions in the best way
possible, and able to bring as much intelligence as possible to bear
on the decision. In Micro-Planner this is done by adding to our
THGOAL statement a recommendation list which can specify that ONLY
certain theorems are to be tried, or that certain ones are to be
tried FIRST in a specified order. Since theorems are programs,
subroutines of any type can be called to help make this decision
before establishing a new THGOAL. Each theorem has a name (in our
definition on page 1, the theorem was given the name THEOREM1), to
facilitate referring to them explicitly.
An important problem is that of maintaining a data base with
a reasonable amount of material. Consider the first example above.
The statement that all humans are fallible, while unambiguous in a
declarative sense is actually ambiguous in its imperative sense (i.e.
the way it is to be used by the theorem prover). The first way is to
simply use it whenever we are faced with the need to prove (FALLIBLE
(THV X)). Another way might be to watch for a statement of the form
(HUMAN (THV X)) to be asserted, and to immediately assert (FALLIBLE
(THV X)) as well. There is no abstract logical difference, but the
impact on the data base is tremendous. The more conclusions we draw
when information is asserted, the easier proofs will be, since they
will not have to make the additional steps to deduce these
consequences over and over again. However since we don't have
infinite speed and size, it is clearly folly to think of deducing and
asserting everything possible (or even everything interesting) about
the data when it is entered. If we were working with totally
abstract meaningless theorems and axioms (an assumption which would
not be incompatible with many theorem-proving schemes), this would be
an insoluble dilemma. But Micro-Planner is designed to work in the
real world, where our knowledge is much more structured than a set of
axioms and rules of inference. We may very well, when we assert
(LIKES (THV X) POETRY) want to deduce and assert (HUMAN (THV X)),
since in deducing things about an object, it will very often be
relevant whether that object is human, and we shouldn't need to
deduce it each time. On the other hand, it would be silly to assert
(HAS-AS-PART (THV X) SPLEEN), since there is a horde of facts equally
important and equally limited in use. Part of the knowledge which
Micro-Planner should have of a subject, then, is what facts are
important, and when to draw consequences of an assertion. This is
done by having theorems of an antecedent type:
(DEFPROP THEOREM2
micro-PLANNER MANUAL 7
(THANTE (X Y) (LIKES (THV X) (THV Y))
(THASSERT (HUMAN (THV X))))
THEOREM)
This says that when we assert that X likes something, we
should also assert (HUMAN (THV X)). Of course, such theorems do not
have to be so simple. A fully general Micro-Planner program can be
activated by an THANTE theorem, doing an arbitrary (that is, the
programmer has free choice) amount of deduction, asssertion, etc.
Knowledge of what we are doing in a particular problem may indicate
that it is sometimes a good idea to do this kind of deduction, and
other times not. As with the CONSEQUENT theorems, Micro-Planner has
the full capacity when something is asserted, to evaluate the current
state of the data and proof, and specifically decide which ANTECEDENT
theorems should be called.
Micro-Planner therefore allows deductions to use all sorts of
knowledge about the subject matter which go far beyond the set of
axioms and basic deductive rules. Micro-Planner itself is
subject-independent, but its power is that the deduction processs
never needs to operate on such a level of ignorance. The programmer
can put in as much heuristic knowledge as he wants to about the
subject, just as a good teacher would help a class to understand a
mathematical theory, rather than just telling them the axioms and
then giving theorems to prove.
Another advantage in representing knowledge in an imperative
form is the use of a theorem prover in dealing with processes
involving a sequence of events. Consider the case of a robot
manipulating blocks on a table. It might have data of the form,
"block1 is on block2," "block2 is behind block3", and "if x is on y
and you put it on z, then x is on z, and is no longer on y unless y
is the same as z". Many examples in papers on theorem provers are of
this form (for example the classic "monkey and bananas" problem). The
problem is that a declarative theorem prover cannot accept a
statement like (ON B1 B2) at face value. It clearly is not an axiom
of the system, since its validity will change as the process goes on.
It must be put in a form (ON B1 B2 S0) where S0 is a symbol for an
micro-PLANNER MANUAL 8
initial state of the world. The third statement might be expressed
as:
(FORALL (X Y Z S)
(AND (ON X Y (PUT X Y S))
(OR (EQUAL Y Z)
(NOT (ON X Z (PUT X Y S))))))
In this representation, PUT is a function whose value is the
state which results from putting X on Y when the previous state was
S. We run into a problem when we try to ask (ON Z W (PUT X Y S)) i.e.
is block Z on block W after we put X on Y? A human knows that if we
haven't touched Z or W we could just ask (ON Z W S) but in general it
may take a complex deduction to decide whether we have actually moved
them, and even if we haven't, it will take a whole chain of
deductions (tracing back through the time sequence) to prove they
haven't been moved. In Micro-Planner, where we specify a process
directly, this whole type of problem can be handled in an intuitively
more satisfactory way by using the primitive function THERASE.
Evaluating (THERASE (ON (THV X) (THV Y))) removes the
assertion (ON (THV X) (THV Y)) from the data base. If we think of
theorem provers as working with a set of axioms, it seems strange to
have function whose purpose is to erase axioms. If instead we think
of the data base as the "state of the world" and the operation of the
prover as manipulating that state, it allows us to make great
simplifications. Now we can simply assert (ON B1 B2) without any
explicit mention of states. We can express the necessary theorem as:
(DEFPROP THEOREM3
(THCONSE (X Y Z)
(PUT (THV X) (THV Y))
(THGOAL (ON(THV X) (THV Z)))
(THERASE (ON (THV X) (THV Z)))
(THASSERT (ON (THVX) (THV Y))))
THEOREM)
This says that whenever we want to satisfy a goal of the form
(PUT (THV X) (THV Y)), we should first find out what thing Z the
thing X is sitting on, erase the fact that it is sitting on Z, and
assert that it is sitting on Y. We could also do a number of other
things, such as proving that it is indeed possible to put X on Y, or
adding a list of specific instructions to a movement plan for an arm
to actually execute the goal. In a more complex case, other
interactions might be involved. For example, if we are keeping
assertions of the form (ABOVE (THV X) (THV Y)) we would need to
delete those assertions which became false when we erased (ON (THV X)
(THV Z)) and add those which became true when we added (ON (THV X)
(THV Y)). ANTECEDENT theorems would be called by the assertion (ON
(THV X) (THV Y)) to take care of that part, and a similar group
called ERASING theorems can be called in an exactly analogous way
when an assertion is erased, to derive consequences of the erasure.
Again we emphasize that which of such theorems would be called is
micro-PLANNER MANUAL 9
dependent on the way the data base is structured, and is determined
by knowledge of the subject matter. In this example, we would have
to decide whether it was worth adding all of above relations to the
data base, with the resultant need to check them whenever something
is moved, or instead to omit them and take time to deduce them from
the ON relation each time they are needed.
Thus in Micro-Planner, the changing state of the world can be
mirrored in the changing state of the data base, avoiding any need to
make explicit mention of states, with the requisite overhead of
deductions. This is possible since the information is given in an
imperative form, specifying theorems as a series of specific steps to
be executed.
If we look back to the distinction between assertions and
theorems made on the first page, it would seem that we have
established that the base of assertions is the "current state of the
world", while the base of theorems is our permanent knowledge of how
to deduce things from that state. This is not exactly true, and one
of the most exciting possibilities in Micro-Planner is the capability
for the program itself to create and modify the Micro-Planner
functions which make up the theorem base. Rather than simply making
assertions, a particular Micro-Planner function might be written to
put together a new theorem or make changes to an existing theorem, in
a way dependent on the data and current knowledge. It seems likely
that meaningful "learning" involves this type of behavior rather than
simply modifying parameters or adding more individual facts
(assertions) to a declarative data base.
micro-PLANNER MANUAL 10
III. The Micro-Planner Primitives
This section will basically be a list of the Micro-Planner
primitives with a detailed description of each. Meta-Linguistic
variables will be enclosed in angle brackets (<>).
The heart of Micro-Planner is a structure known as THTREE; it
is to the hierarchical control structure of PLANNER what a push-down
list is to a recursive control structure such as is found in LISP. In
LISP the push down list remembers the return addresses of recursive
function calls; in Micro-Planner THTREE keeps track of the decisions
(or hypotheses) made so far in the problem-solving process which are
currently considered relevant to the solution. In case a failure
occurs PLANNER can back up THTREE, undoing the decisions which caused
the failure until a promising approach is found. If none is found
the program returns a failure. THTREE is a tree structure, each node
of which contains information about how to proceed in case either
success or failure propagates to that node. Failure is propagated
from a node if and only if a failure propagates to it and no further
possibilities exist at that node. A node of THTREE may be thought of
as a goal, with branches originating at this node associated with
tentatively useful hypotheses for establishing the goal.
Closely associated with THTREE is THALIST, the list of
variable bindings. Certain primitives bind variables by declaration.
In their initial bound state variables are called unassigned and are
assigned to "THUNASSIGNED." THALIST shares the tree structure of
THTREE.
Because of the non-recursive implementation of the
Micro-Planner interpreter the PLANNER value of an expression is not
the same as its LISP value. In most cases this is unimportant because
PLANNER expressions are usually executed for effect rather than for
value. The PLANNER value of an expression is however available as
the LISP value of the LISP free variable THVALUE immediately after
the expression is executed. Although this is not a very pretty
convention it introduces some very great simplifications in the
implementation.
1) (THPROG <variable declaration> <e1> ... <en>)
THPROG is the PLANNER equivalent of the LISP function PROG.
Its job is to bind the variables mentioned in the declaration and
then to execute the expressions <ei> in sequence, unless changes in
sequence are specified by tags and THGO statements. As in LISP,
atoms occuring in THPROG bodies are interpreted as tags. If (THGO
<tag>) is executed at any point in the interpretation of a THPROG,
execution then proceeds from the expression immediately following the
tag <tag>. THGO statements may refer to tags which are not in the
current THPROG but which are in one which called it. The execution
of THPROG terminates either with a failure, successful execution of
its last expression, <en>, or by a forced success with a THRETURN
statement. (THRETURN <exp>) is equivalent to (THSUCCEED THPROG
<exp>) and will cause the THPROG to succeed and return as its PLANNER
value the LISP value of the indicated expression. If a THPROG
returns by succeeding past the last statement, or by executing a
micro-PLANNER MANUAL 11
(THSUCCEED THPROG), it returns as its PLANNER value the atom THNOVAL.
If it fails, it returns NIL.
The variable declaration list is a list of variable
declarations. A variable declaration is either an atom which is the
name of a variable to be used inside the THPROG, or a list of two
elements, the first of which is the variable name and the second of
which is a LISP expression whose LISP value is to be used as the
initial value of the variable. If a variable is bound without giving
it an initial value it is given the default value "THUNASSIGNED."
Evaluation of a THPROG begins at the first expression of the
indicated sequence. If it succeeds, a new branch is generated on
THTREE and the next expression in sequence is evaluated, etc. If any
statement fails then the branches are unwound until either a new
success ends the failure propagation or there are no more branches
and the THPROG fails. Thus THPROG behaves as a THAND with variable
binding capability; it fails unless each of its subexpressions
succeeds, allowing for backup, until it returns. As usual, any LISP
expression may appear in a THPROG; if it evaluates to NIL, a failure
is generated, otherwise a success is assumed. Other relevant
functions are THSUCCEED, THFAIL, THFINALIZE, THGO, and THRETURN.
2) (THAND <e1> ... <en>)
THAND fails unless each of its subexpressions succeeds in
sequence, allowing for backup. It is just like THPROG except that
there are no variable declarations or tags allowed.
3) (THOR <e1> ... <en>)
THOR succeeds if at least one of its subexpressions succeeds.
Basically, it CDRs down the list looking for a winner and if it finds
one it succeeds, returning its value as the PLANNER value. If a
failure propagates back to it, however, it continues CDRing from the
point it left off until it finds another winner or it loses.
4) (THAMONG <variable name> <expression>)
Upon entry the variable named (by an atom) must be bound. If
it is unassigned then it will be assigned to the first member of the
list of choices to which <expression> THVALuates. If the variable
already has a value (is assigned), THAMONG fails unless the assigned
value is already among the choices. Each time a failure backs up to
the THAMONG the variable will be assigned to the next element of the
choice list. If it runs out of choices it fails, otherwise it
succeeds.
5) (THGOAL <pattern> <rec1> ... <recn>)
This is a real dilly to describe. It is probably the most
complex single primitive in Micro-Planner. Assume the simplest case
in which there are no recommendations <reci> given. THGOAL searches
the data base for a datum (i.e. an assertion) which matches the
pattern. If it finds one, it succeeds after assigning all of the
unassigned variables in the pattern so as to make it match the datum;
it then returns the assertion found as its PLANNER value. If it does
not find a matching datum it fails. If after a success, a failure
micro-PLANNER MANUAL 12
propagates back to it, it unassigns the variables it assigned last
time and continues its search for a matching datum from where it left
off.
If recommendations are given they are tried in order. If the
very first recommendation is a (THNODB) or a (THDBF -) the initial
data base search is inhibited, otherwise it is assumed in default.
The possible recommendations are:
1) (THNODB) - Inhibit data base search. If it is not first
it is useless and causes an error.
2) (THDBF <filter>) - Try only those elements of the data
base satisfying the filter.
3) (THTBF <filter>) - Try only those theorems satisfying the
filter.
4) (THUSE <th1> <th2> ...<thn>) - Try the theorems given
explicitly by their atom headers in the order mentioned.
A filter is any unary LISP predicate; the always true
predicate is supplied by the system as THTRUE. All assertions have
property lists which are their CDRs. Thus if a filter refers to the
CDR of its argument it is referring to the property list. CAR of an
assertion, however, is not -1 as in LISP atoms; rather it is the
datum which is matched against the pattern.
If a theorem is recommended, say with THUSE, it had better be
an atom with a THEOREM property pointing to a consequent theorem
(i.e. it must be of the form (THCONSE <variable declarations>
<consequent> <e1> ... <en>))). If the goal pattern matches the
consequent, then the theorem will be tried. The matcher will first
bind the theorem variables appearing in the declaration (see THPROG)
and then match the patterns, causing some of the theorem variables to
be assigned and leaving others unassigned. If the match wins, the
theorem will proceed to execute as a THPROG. If the theorem succeeds
the PLANNER value of the THGOAL will be the pattern of the goal with
the assignments substituted for the assigned variables, unless the
theorem does a THRETURN, in which case the PLANNER value of the
THGOAL will be the goodie returned. If a goal variable which is
unassigned is matched against a theorem variable and the theorem
eventually gives that variable a value then the goal variable also
gets the value. A more detailed description of the matcher will be
given later.
6) (THFIND <mode> <skeleton> <variable declarations> <e1> ... <en>)
THFIND is a primitive whose THVALuation yields a list of
objects, each of which is the result of substituting for variables in
the skeleton values of those variables which cause the program
starting at the variable declarations (like a THPROG) to succeed.
Thus, for example, the data-base contained the assertions (HACKER N)
(HACKER H) (HACKER RG) ( AT MAC RG) and we THVALed the expression
(THFIND ALL (AT SC (THV X)) (X) (THGOAL (HACKER (THV X))) (THNOT
(THGOAL (AT MAC (THV X))))) we would get ((AT SC N) (AT SC H)) as its
THVALUE (PLANNER value). The mode field of a THFIND statement is a
triplet (<at least> <at most> <result>). THFIND fails unless it
finds at least a number equal to CAR of the mode and if it finds
greater than or equal to CADR of the mode it returns CADDR of the
micro-PLANNER MANUAL 13
mode. If CADR of the mode is not a number it will never be found.
The mode triplet may be abbreviated by ALL = (1 NIL NIL), any number
n = (n n T).
7) (THCOND <pair1> ... <pair n>)
THCOND is the PLANNER analogue of COND in LISP. As in
Stanford LISP the "pairs" needn't be. Basically THCOND executes the
CAR of each pair until one succeeds. The THCOND will then succeed if
all the rest of that "pair" succeeds (like a THAND) else THCOND will
fail.
8) (THNOT <e>) is defined as (THCOND (<e> (THFAIL)) ((THSUCCEED))).
9) (THASSERT <skeleton> <rec1> ... <recn>)
THASSERT adds the assertion (formed by substituting
assignments for variables (or by THVALing (THEV 's) as described in
the matcher section) in the skeleton) to the data-base except if the
skeleton is an atom, in which case it adds the atom as a theorem to
the theorem base.
THASSERT only fails if it tries to assert an already existing
assertion. If the first recommendation to a THASSERT is a (THPROP
<e>) then the LISP value of <e> is used as the property list of the
assertion being asserted. THASSERT also may recommend antecedent
theorems with THTBF or THUSE as in THGOAL, though the success or
failure of those theorems is irrelevant to success or failure of the
assertion. The PLANNER value of a THASSERT is the object asserted.
10) (THERASE <skeleton> <rec1> ... <recn>) is identical to THASSERT
except for effect. If a failure backs up to an assertion or an
erasure it is undone.
11) (THDO <e1> ... <en>)
THDO executes each of its subexpressions in turn and cares
not whether they succeed or fail; it then succeeds. If a failure
backs up to it, all that it did is undone.
12) (THAPPLY <theorem> <datum>) calls the specified theorem causing
it to match its pattern to the specified datum. If it matches the
theorem is executed with <datum> as its "argument." The THVALUE of a
THAPPLY is the value of the theorem applied.
13) THPUTPROP, THREMPROP, THRPLACA, THRPLACD are just like their LISP
counterparts except that if a failure backs up to them they undo
their effect.
14) (THSETQ <var1> <e1> ... <varn> <en>)
Sets variable 1 to the value of e1 and ... and sets variable
n to the value of en. Undone if failure backs up to it. If the
variable is a planner variable then the corresponding expression is
THVALed; otherwise the expression is EVALed. See warning about
THVAL.
micro-PLANNER MANUAL 14
15) (THVSETQ <var1> <e1> ... <varn> <en>)
Sets the variables to the values of eis as in THSETQ. Not
undone on failure backup. See warning about THVAL.
16) (THV <variable name>) (THNV <variable name>)
These LISP functions get the PLANNER value of the variable
whose name is given. The atoms THV and THNV also serve as markers of
the special variable flags to the matcher.
17) (THVAL <expression> <alist>)
THVAL is the Micro-Planner evaluator just as EVAL is the LISP
evaluator. As in LISP, the first argument is evaluated (THVALuated)
with free variables in it given the values associated with them on
the given alist. Micro-Planner's alist, called THALIST, is a list of
pairs (CAR-CADR not CAR-CDR) of variable names and values. If an
error occurs while THVALing an expression, an error message is
printed and THVAL goes into its listening loop. The next expression
to be executed is in the variable THE. To proceed, type T<space>; to
terminate the calculation by failure type NIL<space>. Warning: an
explicit call to THVAL may not be reentered for backup upon failure
after that call returns.
18) (THUNIQUE <variable name>)
THUNIQUE is a primitive by which a user may test to see if he
is in one kind of infinite loop. THUNIQUE assumes that the variable
given is bound. If the variable is bound, it is assumed that it is
assigned to a list of atoms and expressions. THUNIQUE will then fail
if there is any previous binding and assignment of the given variable
for which the atoms and expressions THVALuate identically, the atoms
beng interpreted as variables.
19) (THFINALIZE <arg1> <arg2>)
THFINALIZE is a primitive which allows pruning of THTREE.
Essentially, if one THFINALIZES, say to a tag, then all the things
done since that tag was passed are not undoable in case of failure.
Example: To put all of the green blocks in the box and return a list
of those actually moved:
(THPROG (X (Y NIL))
(THOR (THAND (THGOAL (IS (THV X) BLOCK))
(THGOAL (COLOR (THV X) GREEN)))
(THRETURN (THV Y)))
FOO
(THCOND ((THGOAL (CONTAIN BOX (THV X))) (THFAIL))
((THGOAL (PUTIN (THV X) BOX) (THUSE TC-PUTIN))
(THSETQ (THV Y) (CONS (THV X) (THV Y)))
(THFINALIZE THTAG FOO)
(THFAIL))
((PRINT (THV X)) (THERT CAN NOT PUT IT IN))))
micro-PLANNER MANUAL 15
(THERT is an error function that prints out its argument as an error
message and enters the THVAL listening loop for further instructions.)
Besides finalizing to a tag, one can finalize a theorem or a
THPROG by saying (THFINALIZE THEOREM) or (THFINALIZE THPROG). There
are lots of other things that can be done with THFINALIZE, but I will
not guarantee them.
20) (THSUCCEED <arg1> <arg2>)
THSUCCEED caused success to propagate, the extent of which is
determined by the arguments:
(THSUCCEED THTAG <tag>) = (THGO <tag>) - see THPROG.
(THSUCCEED THPROG <e>) = (THRETURN <e>) - see THPROG.
(THSUCCEED <place>) = (THSUCCEED <place> T)
(THSUCCEED THEOREM <e>) causes theorem to succeed with value of <e>.
(THSUCCEED THEOREM) causes the theorem to succeed with value THNOVAL.
(THSUCCEED) causes a simple success to propagate.
21) (THFAIL <arg1> <arg2> <arg3>)
THFAIL causes failure to propagate, the extent of which is
determined by the arguments:
(THFAIL THTAG <tag> T) causes a failure to propagate to the
tag indicated.
(THFAIL THTAG <tag>) causes a failure to propagate past the
tag indicated.
(THFAIL THPROG), (THFAIL THEOREM) cause the THPROG or the
THEOREM currently in to fail.
(THFAIL THINF) causes failure to top level of THVAL.
(THFAIL THMESSAGE <message>) causes a failure to propagate
until it reaches a THMESSAGE statement whose pattern matches the
message.
22) (THMESSAGE <variable declarations> <pattern> <e1> . . . <en>)
examines failures propagating to it, if one has a message which
matches the pattern (after the declarations are made) control then
passes to the body, <ei>, which executes as a THPROG.
micro-PLANNER MANUAL 16
23) (THGO <tag>) = (THSUCCEED THTAG <tag>)
24) (THRETURN <e>) = (THSUCCEED THPROG <e>)
25) (THASVAL <variable>)
THASVAL is a predicate which assumes that the indicated
variable is bound. It succeeds if and only if the variable is
assigned a value.
26) (THFLUSH <indicator1> <indicator2> ...)
THFLUSH is a generally useful function for getting a LISP
into some desired state. It remprop's all properties with the
indicators specified from all atoms on the OBLIST.
27) (THDUMP) dumps the state of a Micro-Planner as to assertions and
theorems on the currently selected output devices.
28) (THDATA) causes Micro-Planner to go into a read loop for gobbling
assertions and theorems at high speed. Loop ends when NIL is read.
29) (THBKPT <comment>) has no effect unless THTRACEd. If it is, a
THBKPT becomes a comment which is typed out and which breaks if
desired.
30) THEOREMS
Theorems are the Micro-Planner analogue of functions in LISP.
There are three kinds:
consequent theorem - for establishing goals
antecedent theorems - for expanding on assertions
erasing theorems - for expanding on erasures.
Theorems are defined by (DEFPROP <name> <body> THEOREM) and are added to
the data-base using THASSERT or THDATA and may be removed with THERASE.
The form of a theorem is (<indicator> <variable declarations> <pattern>
<e1> ... <en>), where the indicator may be THCONSE, THANTE, or THERASING,
whichever is appropriate. When a theorem is called the declared
variables are bound and thee pattern is matched to the calling pattern in
THGOAL or datum in THASSERT, THERASE, and THAPPLY. This has the effect
of assigning some of the theorem's variables. The theorem is then
executed as a THPROG if the match succeeds.
31) The Matcher
The Matcher in Micro-Planner is elementary and contains a
minimum of bells and whistles but is (hopefully) sufficiently
powerful for most problems. If more powerful matching capabilities
are needed, hooks are provided for the user to hang himself by. (If
you wish to hang yourself come see me first! If you really need
hair, wait for Hewitt's PLANNER.) Micro-Planner's matcher only
matches lists one level deep and only has two distinct kinds of
variable occurrences. The matcher's actions can be summarized in the
6-by-6 chart on the next page, which shows how any two pattern
elements interact. One nice hook in the matcher is that a pattern
micro-PLANNER MANUAL 17
element (or the entire pattern) may be of the form (THEV
<expression>),
which means that the element (or pattern) is to be
replaced with the result of THVALuating the expression with an
appropriate THALIST. For example, to stack up all red objects:
(THGOAL (STACKUP
(THEV (THFIND ALL
(THV X)
(X)
(THGOAL (COLOR (THV X) RED)))))).
micro-PLANNER MANUAL 18
MATCHER CHARACTERISTICS
(insert XEROXed page of incomprehensible chart at this page)
micro-PLANNER MANUAL 19
IV. A Compendium of Micro-Planner Error Comments
The Micro-Planner error comments are meant to be
self-explanatory. If you come across one which is not, it is
probably meant for me, not you, and it would help in removing
residual bugs for you to save the situation and show it to me. All
Micro-Planner error comments are typed out by a break function called
THERT which leaves you in a LISP listen loop at a point as close as
possible to the occurrence of the error, so that the state of the
system may be interrogated. Usually the error is fatal, but if you
wish to proceed, type T<space>. By typing NIL<space> at the listen
loop the program will be aborted by infinite failure in an effort to
restore the data base. Usually something is typed out before the
error comment; that is the object the comment is complaining about.
Micro-Planner error comments almost always end with - <funny word>;
the <funny word> is the name of the system function which got mad.
The authorized list follows:
LISPERROR - THVAL
LISP became unhappy when trying to evaluate the expression
typed out.
BAD SUCCEED - THVAL, or BAD FAIL - THVAL
You were screwed by a Planner bug. Please save situation and
contact me.
UNCLEAR RECOMMENDATION - THTRY
The expression typed out before the error comment was a
recommendation to THGOAL which was not either a THTBF, THDBF, or a
THUSE, or was a THNODB which did not come first in the list.
BAD THEOREM - THTRY1
The expression printed was passed to THGOAL as a THEOREM. It
either did not have a THEOREM property or was not a consequent
theorem.
NOT FOUND - THUNIQUE
The expression printed out was passed to THUNIQUE as the
reference variable; unfortunately it was unbound.
THUNBOUND - THUNIQUE
The variable printed out was unbound. It was accessed by
THUNIQUE.
BAD CALL - THFINALIZE
You called THFINALIZE without giving a place to finalize to.
OVERPOP - THFINALIZE
THFINALIZE overpopped THTREE trying to find the lousy place
to stop.
micro-PLANNER MANUAL 20
OVERPOP - THSUCCEED
THSUCCEED overpopped THTREE trying to find the place to stop
succeeding. Remember that THGO and THRETURN use THSUCCEED.
OVERPOP - THFAIL
THFAIL overpopped THTREE trying to find a place to stop
failing.
IMPURE ASSERTION OR ERASURE - THASS1
The datum you tried to assert or erase had a variable which
was unassigned.
BAD THEOREM - THTAE
You tried to call an antecedent or erasing theorem which was
of the wrong type or did not have a theorem property.
UNCLEAR RECOMMENDATION - THTAE
You gave a THASSERT or THERASE recommendation which was not a
THTBF or a THUSE.
ODD NUMBER OF GOODIES - THSETQ, or ODD NUMBER OF GOODIES - THVSETQ
THSETQ or THVSETQ does not know what to do with the last goodie.
THUNBOUND - THV1
You tried to access the value of the unbound variable
printed.
THUNASSIGNED - THV1
You tried to use the value of the unassigned variable
printed.
OVERPOP - THREMBIND
Probably a Planner bug. Refer problem to RPO.
THUNBOUND - THGAL
You tried to access the unbound variable printed.
micro-PLANNER MANUAL 21
V. Hints and Kinks
1) All atoms whose pnames begin with TH are property of
Micro-Planner and should not be used in programs designed to interact
with it.
2) When Micro-Planner is run (by typing "R PLNR") it is
listening in a READ-THVAL-PRINT loop at the top level. Typing
T<space> will cause this loop to be exited to a LISP READ-EVAL-PRINT
loop. To re-enter the READ-THVAL-PRINT listen loop execute the
function "(THINIT)" or "(RESTART)"; the difference being that
(THINIT) removes all PLANNER trace/break conditions (see paragraph 4
below).
3) The EXPR version of Micro-Planner is in
PLNR.135[P,RPO] and the LAP version is stored in PLNR.LAP[P,RPO].
This manual is PLNR.MEM[P,RPO].
4) Because most Micro-Planner primitives operate by
modifying THTREE and then returning, it is fairly unilluminating to
try to trace them with a LISP tracer (which is good for the LISP
recursive control structure). For that reason I have taken pains to
provide a tracer which is more relevent to the PLANNER control
structure. It is available as EXPR code in THTRAC.13[P,RPO]. With it
one can conditionally trace and break on theorems, assertions,
erasures, and goals. The tracer file is read in automatically when
called the first time.
To use the tracer incant (THTRACE <obj1> . . . <objn>), where each
object is an item to be traced or broken at. The possible entries
are either:
<atom> abbreviation for (<atom> T NIL)
(<atom> <trace condition>) short for (<atom> <trace condition> NIL)
(<atom> <trace condition> <break condition>)
The CAR of the item may either be the name of a theorem or one of the
following atoms which have special meanings:
THEOREM all theorems
THGOAL all goals
THASSERT all assertions
THERASE all erasures
THBKPT all breakpoints
The conditions are THVALed with the THALIST which is current at the
time of call and thus may be arbitrary PLANNER programs which test
the state of variables and the data base. Tracing of selected items,
or of all items may be terminated using THUNTRACE.
5) A Micro-Planner program may at any point call a LISP
program, but a LISP program may not call a Micro-Planner primitive
because the PLANNER control structure is not really recursive. If a
micro-PLANNER MANUAL 22
LISP routine wishes to call a PLANNER program it must explicitly
THVAL it with an appropriate THALIST. Be especially careful not to
screw around with the LISP values of Micro-Planner primitives unless
you understand what you are doing. The possibilities for lossage are
infinite.
micro-PLANNER MANUAL 23
APPENDIX A: ADDITIONS TO MICRO-PLANNER
Observations on new features noticed in micro-PLANNER, version #135:
1) THPSEUDO
If a THASSERT (or THERASE) contains the element "(THPSEUDO)" as the
first recommendation in the recommendation list, then the pattern is
not inserted (erased) into (from) the data base,the data base is not
even referenced, and the pattern doesn't have to be "pure"*, but the
rest of the mechanism proceeds as usual; viz, the rest of the
recommendation list is processed with respect to the supplied
pattern. That is, the recommended theorems are applied to the
pattern. As usual, the recommendations are via "(THTBF <unary
predicate>)" or "(THUSE <theorem name 1><theorem name 2>...)".
* A pure pattern contains bound variables , has a THEV, THV, or THNV
form, or has a LISP function name as its first element with the
remaining elements the arguments to the function and which results in
a pure pattern.
[NOTE: THV and THNV are identical in micro-PLANNER !!!].
2) THAUX
This atom is used as an indicator to allow user defined functions to
replace those supplied as part of the micro-PLANNER system. The
following gives examples of how the code indicates THAUX may be used
(manual describing these features no available yet, i think):
If a pattern has the form:
"(THAUX <atom> <pattern>)"
then
(GET <atom> @THMATCHLIST) is used as the function instead of the
standard micro-PLANNER function THMATCHLIST. The auxiliary function
should expect two arguments: <pattern> and the type, i.e. THANTE,
THCONSE, or THERASING. It should return a list of theorem names
suitable for the <pattern>.
or
(GET <atom> @THADD) instead of, and in, THADD. Similar to above.
or
(GET <atom> @THREMOVE) instead of, and in, THREMOVE. Similar to above.
[NOTE: see the micro-PLANNER expr code for THADD, THREMOVE, and
THMATCHLIST].
micro-PLANNER MANUAL APPENDIX A A-1
3) THPROP
An assertion can have the following form in its recommendation list
(near the beginning of the list):
"(THPROP <atom>)".
The <atom> is EVALed and should yield a list of property indicators and
values:
"(<indicator> <value> ....<indicator> <value>)".
These indicator/value pairs are put on the property list of the theorem
or pattern being THASSERTed.
4) THRESTRICT
This indicator occurs in the function THBIND,THMATCH2, THMATCHLIST.
what does it do???
5) THNOHASH
tired of left-overs ?? buried deep within THIP along with:
RETURN THBQF
RETURN THOK
THIP is called by THADD, its argument being each element of a pattern. Consider
the case of asserting a theorem. If an atom has the property THNOHASH for the tag
THANTE, THCONSE, or THERASING, then that atom is incapable of being an index
for theorem patterns (that is, theorems can't be referenced using that atom
even though the atom appears in the defining pattern of the theorem). THADD
stops what it is doing if THIP returns NIL. That's why the atoms are returned
instead. NIL is returned when a data base assertion is done (i think). If
a THV, THNV, or ? occurs, then return THVRB; when THNOHASH occurs return THBQF;
otherwise return THOK (strange mneumonics).
micro-PLANNER MANUAL APPENDIX A A-2
THE, THSTEP, THSTEPD, THSTEPT, THESTEPF
These are global variables useful for bypassing, or augmenting the normal
action of THVAL.
As a review, the main loop of THVAL can be summarized as follows:
1. THE←THEXP; THEXP←NIL; where THEXP is initially the argument to THVAL.
2. if THSTEP is non-nil then it is EVALed.
3. THVALUE←(EVAL THE).
If this results in an error or (ERR NIL), then a continuable halt
is generated in the guise of "LISPERROR - THVAL".
[T=success (proceed), NIL=fail (backup)].
4. If non-nil, THSTEPD is now EVALed.
5. test for finite or success, then/else loop
THEXP contains functions generated by the micro-PLANNER interpreter to
be evaluated, and THVAL loops. Or if nil, and THVALUE is non-nil
then a success happens, else a failure happens.
When a success occurs, THSTEPT is EVALed if non-NIL and THVAL loops.
When a failure occurs, THSTEPF is EVALed if non-NIL and THVAL loops.
This is somewhat of a simplification to show in what order these user-
setable variables are executed. For more detail consult the code,
PLNR.135[P,RPO] or me.
micro-PLANNER MANUAL APPENDIX A A-3
MICRO-PLANNER AT STANFORD
CONTENTS...
micro-PLANNER FILES
SYSTEM DUMP
micro-PLANNER FUNCTIONS
micro-PLANNER MANUAL
COMPILING A micro-PLANNER
TRACE/BREAK
A micro-PLANNER PROGRAM
micro-PLANNER MANUAL APPENDIX B B-1
Micro-PLANNER is a goal-directed, LISP-embedded language that was
created at MIT as a subset of Carl Hewitt's PLANNER. Micro-PLANNER
has been imported to Stanford and will run in Stanford's LISP with
the help of a compatibility file.
micro-PLANNER FILES
All files relating to micro-PLANNER can be found on disk area [P,RPO].
PLNR.MEM the micro-PLANNER programming language manual.
See micro-PLANNER manual below.
PLNR.135 the current s-expression version of micro-PLANNER
PLNR.LAP the compiled version
CONVRT.LSP the s-expression file that makes STANFORD LISP look
like MIT's MACLISP
CONVRT.LAP the compiled version
FIXUP.COM this file must be read into the LISP compiler before
compiling either PLNR.135 or CONVRT.LSP. See COMPILING
below.
THTRAC.13 this is a tracing package that allows the tracing and
breaking at selected or all Goals, Assertions,
Erasings, Theorems, or break points. See TRACING
below.
micro-PLANNER MANUAL APPENDIX B B-2
SYSTEM DUMP
To run micro-PLANNER, type "R PLNR <RETURN>" at monitor level. A
system dump of micro-PLANNER is loaded and started, and the function
(THINIT) is evaluated, making the micro-PLANNER function THVAL the
evaluator in the top level "read - evaluate - print" loop.
The file CONVRT.LSP (and .LAP) contains a command to put the SWAPIT
property on the property list of the atom THEOREM, so the SOS-LISP
link will work for any PLNR dump for user defined theorems. To make
GRINDEF and ALVINE work for THEOREMs requires that THEOREM be added
to the list of indicators, %%%L. (See the LISP manual).
The system dump of micro-PLANNER was created by the following formula:
R LISP 33 <RETURN>
Y
2000 <SPACE>
15000 <SPACE>
<SPACE>
<SPACE>
<SPACE>
(DSKIN (CONVRT.LAP)(PLNR.LAP)) <RETURN>
(INITFN @(LAMBDA () (PROG ()(INITFN NIL)(THINIT)))) <RETURN>
<CALL>
SAVE PLNR[1,3] <RETURN>
It takes about 30 seconds of machine time to LAP in the two files.
micro-PLANNER MANUAL APPENDIX B B-3
LISP TOP-LEVEL micro-PLANNER FUNCTIONS
(THINIT) and (RESTART) are the two functions for entering the
"read - THVAL - print" loop from LISP. Typing "T <RETURN>" will
exit to the "read - EVAL - print" loop of LISP. The main differences
in the two functions are the message printed out by THVAL and that
THINIT terminates all micro-PLANNER tracing/breaking.
As an aid for knowing whether EVAL or THVAL is listening, THVAL
prints "n!*" when ready for input, where n is the level of recursion.
THVAL enters itself when an error occurs so that the value of
variables can be checked with the current THALIST. When such a
recursion occurs, typing "T" or "NIL" will continue (with that value,
if THVAL is looking for a value).
micro-PLANNER MANUAL APPENDIX B B-4
micro-PLANNER MANUAL
To get a copy of the manual type "XEROX PLNR.MEM[P,RPO] <RETURN>" to
the monitor. The manual is twenty pages long. This is the manual as
received from MIT but edited to reflect the changes caused by imple-
menting micro-PLANNER in STANFORD LISP.
There are two appendices. Appendix A details some new features noticed
in the micro-PLANNER code but not described in the manual. Appendix
B is this blurb, containing more mundane details of the micro-PLANNER
implementation.
micro-PLANNER MANUAL APPENDIX B B-5
COMPILING A micro-PLANNER
Start the LISP compiler, read in the file FIXUP.COM to make it
compatible with the MACLISP of PLNR.135 and compile the file
by typing "(COMPL (PLNR./135))".
(If there is a complaint that some function is undefined, and the
compilation terminates, the function is probably defined in
CONVRT.LSP, so read it in).
micro-PLANNER MANUAL APPENDIX B B-6
TRACE/BREAK
This is a short version of the trace package described on page 20 of
the manual. To use the tracer, evaluate (THTRACE <obj1> ... <objn>),
which automatically reads in THTRAC.13, if it is not already present.
Each <obji> is an item to be traced or broken at. The possible
entries are either:
<atom> abbreviation for (<atom> t nil)
(<atom> <trace condition>) abbrev. for (<atom><trace condition> nil)
(<atom><trace condition><break condition>)
The CAR of the item may either be the name of a theorem or one of the
following atoms which have special meanings:
THEOREM all theorems
THGOAL all goals
THASSERT all assertions
THERASE all erasures
THBKPT all breakpoints
The conditions are THVALed with the THALIST which is current at the
time of call and thus may be arbitrary micro-PLANNER programs which
test the state of variables and the data base. Tracing of selected
items, or of all items may be terminated using THUNTRACE, or exiting
from the "read - THVAL - print" loop and re-entering via (THINIT),
instead of (RESTART). The global variable THTRACE is a list of
trace/break conditions. (THINIT) SETQs this variable to NIL.
micro-PLANNER MANUAL APPENDIX B B-7
A micro-PLANNER PROGRAM - BLOCKS by TERRY WINOGRAD
A program for manipulating blocks with a computer arm was written by
one of the micro-PLANNER implementers. It demonstrates how LISP
functions and micro-PLANNER theorems and be combined. And it works.
The result of THVALing one of the action THGOALs listed below, is to
construct a sequence of actions (robot primitives, that if executed,
would achieve the goal. The primitives are:
1) (GRASP <obj>)
2) (UNGRASP)
3) (MOVETO <x> <y> <z>) COMMENT destination of the hand and
whatever it may be grasping;
If the THGOAL succeeds, the global variable PLAN is the reverse of
the desired sequence. The micro-PLANNER and LISP program is
BLOCK.THM[H,RPO] & BLOCK.LSP[H,RPO] and a reasonable data base is
DATA.TW[H,RPO]. (The necessary THASSERTs are done as the file is read
in).
Defined THGOALs are:
ACTIONS
(#GRASP <obj>)
(#UNGRASP)
(#RAISEHAND)
(#PICKUP <obj>)
(#PUT <obj><place>)
(#PUTON <obj_source><obj_destination>)
(#CLEARTOP <obj>)
(#GET-RID-OF <obj>)
(#FINDSPACE <surface><obj_size><obj><space>)
(#MOVEHAND <place>) COMMENT the hand and its contents;
(#MOVEHAND2 <place>) COMMENT just the hand;
PRIMITIVES
(#AT <obj> <place>)
(#COLOR <obj><color>)
(#SIZE <obj><size>)
(#GRASPING <obj>)
(#SHAPE <obj><shape>)
(#MANIP <obj>)
(#SUPPORT <obj_below><obj_above>)
(#ON <upper_obj><lower_obj>)
(#IS <obj><type>)
KEY:
<obj>=object name
<place>=(<x> <y> <z>), i.e. the position
<color>=#RED|#WHITE|#BLUE|#GREEN
<type>=#BLOCK|#PYRAMID|#BOX
<shape>=#POINTED|#RECTANGULAR
micro-PLANNER MANUAL APPENDIX B B-8
<size>=(<∂x> <∂y> <∂z>)
<space> is the value returned
#SUPPORT tests adjacent blocks
#ON tests a chain of support
All object name atoms begin with ":", such as ":B1" or ":BOX". The
sharp sign,"#", was used by the writer of BLOCKS to indicate these
are reserved words in his programs. These are not inherent to
micro-PLANNER. Also ":" and "#" need not be part of an atom name;
any LISP atom is legal.
GLOBAL VARIABLES
HANDAT is the current x,y,z position of the hand
ATABLE is a list of items, each being (<obj><place><size>)
PLAN is the reverse of the sequence of actions, in robot primitives,
needed to achieve the goal
AN EXAMPLE
This example shows what would be typed to clear the top of block :B1
COMPUTER TYPEOUT USER TYPEIN
To initialize the world:
.
R PLNR <RETURN>
MICRO-PLANNER
>>> TOP LEVEL
LISTENING THVAL
0!* (DSKIN (P RPO)(BLOCK.THM)(BLOCK.LSP)(DATA.TW))
lots of type out from THASSERTions
FILES-LOADED
0!*
now to do a THGOAL
(THGOAL (#CLEARTOP :B1)(THTBF THTRUE))
think,think,think for 3 seconds
((#CLEARTOP :B1))
0!* PLAN
((UNGRASP)(MOVETO <place>)(GRASP (QUOTE :B1))(MOVETO <place>)
0!* T
EXIT
*
micro-PLANNER MANUAL APPENDIX B B-9